
var jBitstream = function(buffer) {
	if (!(this instanceof arguments.callee)) {
		throw new Error("Constructor may not be called as a function");
	}

	if (!(buffer instanceof jDataView)) {
		throw new TypeError('Type error');
	}
	this._buffer = buffer;
	this._offset = 0;
	this._current_byte = 0;
	this._count = 0;
};

jBitstream.prototype = {
	next : function() {
		if (this._offset == 0) {
			this._offset = 8;
			this._current_byte = this._buffer.getUint8();
		}
		this._count += 1;		
		this._offset -= 1;
		var ret = (this._current_byte & 0x80) >> 7;
		this._current_byte = (this._current_byte & 0x7F) << 1;
//		console.log("decode", ret);
		return ret;
	},
	
	end : function(bitlen) {
/*		
		if (this._offset == 0 &&
			this._buffer.tell() == this._buffer.byteLength) {
			return true;
		} else {
			return false;
		}
*/		
		return bitlen <= this._count;
	}
};

var jHuffmanDecoder = function(name) {
	if (!(this instanceof arguments.callee)) {
		throw new Error("Constructor may not be called as a function");
	}
		
//	this._dictionary = {};
	this._keys = [];
	this._symbols = [];
	this._trie_root = null;
	this._name = name;
};

jHuffmanDecoder.prototype = {
	build_trie : function(keys, symbols, lb, rb, pos, keystring) {
		var node = new Object();
		if (lb == rb) {
			node.is_children = true;
			node.symbol = symbols[lb];
			node.index = lb;
//			console.log(keystring, node.symbol);			
		} else {
			node.is_children = false;
			var mid = lb;
			while (mid < rb && keys[mid][pos] == keys[mid+1][pos])
				mid += 1;
			node.lchild = this.build_trie(keys, symbols, lb, mid, pos+1, keystring+'0');
			node.rchild = this.build_trie(keys, symbols, mid+1, rb, pos+1, keystring+'1');		
		}
		return node;
	},

	set_dict : function (keys, symbols) {
		this._keys = keys;
		this._symbols = symbols;
		this._trie_root = this.build_trie(keys, symbols, 0, keys.length-1, 0, '');
	},

	decode : function (bitstream) {
		var node = this._trie_root;
		while (!node.is_children) {
			var now = bitstream.next();
			if (now == 0) {
				node = node.lchild;
			} else {
				node = node.rchild;
			}
		}
		return [node.symbol, node.index];
	}
}

var jPipeDecoder = function() {
	if (!(this instanceof arguments.callee)) {
		throw new Error("Constructor may not be called as a function");
	}
		
	this._length_decoder = new jHuffmanDecoder('length');
	this._val_decoder = new jHuffmanDecoder('value');
	this._bwt_size = 513;
};

jPipeDecoder.prototype = {
	read_dictionary : function(buffer, valtype) {

		var num_entries = buffer.getUint32();
		console.log("num_entries="+num_entries);

		keys = [];
		symbols = [];
		for (var i = 0; i < num_entries; ++i) {
			var key_length = buffer.getUint32();
            //console.log("key_length=" + key_length);

			var key = "";
			for (var j = 0; j < key_length; ++j) {
				key += buffer.getChar().toString();
			}
            //console.log("key =" + key);

			var val = 0;
			if (valtype == 0) {
				val = buffer.getUint32();
			} else {
				val = buffer.getFloat32();
			}
            //console.log("val =" + val);

			keys.push(key);
			symbols.push(val);

            console.log("key="+key+" val="+val);
		}
		return [keys, symbols];
	}, 

	decode : function(buffer) {
		// Read the first value
		var initial_val = buffer.getFloat32();
		console.log("initial_val="+initial_val);

		// Parse Huffman Dictionary, symbol dict
		console.log("read sym dict!");
		var dict = this.read_dictionary(buffer, 1);
		this._val_decoder.set_dict(dict[0], dict[1]);


		// Parse Huffman Dictionary, len dict
		console.log("read len dict!");
		dict = this.read_dictionary(buffer, 0);
		this._length_decoder.set_dict(dict[0], dict[1]);
		
		// Build BWT symbol tables;
		var symbol_strings = []
		var sym_index = [];
		var bwt_index = [];
		var bwt_rindex = [];
		for (var i = 0; i < this._val_decoder._symbols.length; ++i) {
			symbol_strings.push(this._val_decoder._symbols[i].toString());
			sym_index.push(i);
			bwt_index.push(i);
			bwt_rindex.push(0);
		}
		var sort_function = function(a, b) {
			return symbol_strings[a] > symbol_strings[b];		
		}
		sym_index.sort(sort_function);
		var sym_eof = 0;
		for (var i = 0; i < sym_index.length; ++i) {
			bwt_index[sym_index[i]] = i;
			bwt_rindex[i] = sym_index[i];
			if (symbol_strings[sym_index[i]] == 'Infinity') {
				sym_eof = i; 
			}
		}
		console.log('symbols', symbol_strings, 'sym_index', sym_index, 'sym_eof', sym_eof);
		console.log('bwt_index', bwt_index, 'bwt_rindex', bwt_rindex);
		
		// Decoding Run Length and BWT:
		var bitstream_len = (buffer.getUint32()-1) / 
          (this._bwt_size-1) * (this._bwt_size);
        console.log("bitstream_len="+bitstream_len);
		var bitstream = new jBitstream(buffer);
		var ret_array = [initial_val];
		var decode_buffer = [];
		var num_val_symbols = this._val_decoder._symbols.length;
		console.log('decode');
		while (!bitstream.end(bitstream_len)) {
			var val_decode = this._val_decoder.decode(bitstream);
			var value = val_decode[1];
			var len = this._length_decoder.decode(bitstream)[0];
      if (bwt_index[value] == sym_eof)
        console.log('eof', decode_buffer.length, len);
			for (var i = 0; i < len; i++) {
				decode_buffer.push(bwt_index[value]);
			}
			if (decode_buffer.length >= this._bwt_size) {
				var after_bwt = this.decode_bwt(decode_buffer, this._bwt_size,
												num_val_symbols, sym_eof);
				decode_buffer.splice(0, this._bwt_size);
				for (var i = 0; i < this._bwt_size - 1; ++i) {
					ret_array.push(this._val_decoder._symbols[bwt_rindex[after_bwt[i]]]);
				}
			}
		}
		if (decode_buffer.length > 0) {
			var after_bwt = this.decode_bwt(decode_buffer, decode_buffer.length, 
											num_val_symbols, sym_eof);
			for (var i = 0; i < after_bwt.length-1; ++i) {
				ret_array.push(this._val_decoder._symbols[bwt_rindex[after_bwt[i]]]);
			}		
		}
		
		// Delta decompression
		
		for (var i = 1; i < ret_array.length; ++i) {
			if (ret_array[i] == Infinity) {
				ret_array[i] = 0;
			}
			ret_array[i] += ret_array[i - 1];
		}
		
		return ret_array;
	},
	
	decode_bwt : function(decode_buffer, decode_len, num_symbols, sym_eof) {
		console.log('bwt', num_symbols, decode_len, decode_buffer.length, sym_eof);
    for (var i = 0; i < decode_len; ++i) {
      if (decode_buffer[i] < 0 || decode_buffer[i] >= num_symbols) {
        console.log('wrong', i);
      }
    }
    var firstcol = []
    for (var i = 0; i < decode_len; ++i)
      firstcol.push(decode_buffer[i]);
		firstcol.sort();
		var count = [];
		var byteStart = [];
		for (var i = 0; i < num_symbols; ++i) {
			count.push(0);
			byteStart.push(-1);
		}
		var output = [];
		for (var i = 0; i < decode_len; ++i) {
			output.push(0);
		}
		var shortcut = [];	
		for (var i = 0; i < decode_len; ++i) {
			var shortcutIndex = decode_buffer[i];
			shortcut.push(count[shortcutIndex]);
			count[shortcutIndex] += 1;
			shortcutIndex = firstcol[i];
			if (byteStart[shortcutIndex] == -1) {
				byteStart[shortcutIndex] = i;
			}
		}
		var localIndex = -1; 
    for (var i = 0; i < decode_len; ++i)
      if (decode_buffer[i] == sym_eof) {
        localIndex = i;
        break;
      }
    if (localIndex == -1) {
      for (var i = 0; i < decode_len; ++i)
          output.push(0);
      return output;
    }
		for (var i = 0; i < decode_len; ++i) {
			var nextByte = decode_buffer[localIndex];
			output[decode_len-i-1] = nextByte;
			shortcutIndex = nextByte;
			localIndex = byteStart[shortcutIndex] + shortcut[localIndex];
		}
		return output;
	}
};
